#include <iostream>
#include <memory.h>
#include "mgraph.cpp"

using namespace std;

Status GetShortestPath(MGraph graph);

int main()
{
	MGraph graph(UDN);
	int i;
	int arcs[9][3]={
		{0,1,1},
		{0,2,4},
		{1,2,2},
		{1,3,7},
		{1,4,5},
		{2,4,1},
		{3,4,3},
		{3,5,2},
		{4,5,6}
	};
	Status st;
	for(i = 0; i <= 5; i++)
	{
		st = graph.InsertVex(i);
		if(st != OK)
			cout << "Error in inserting vertex." << endl;
	}
	for(i = 0; i <= 8; i++)
	{
		st = graph.InsertArc(arcs[i][0], arcs[i][1], arcs[i][2]);
		if(st != OK)
			cout << "Error in inserting arc." << endl;
	}
	GetShortestPath(graph);
	return 0;
}

Status GetShortestPath(MGraph graph)
{
	bool visited[MAX_VERTEX_NUM]={0};
	int dist[MAX_VERTEX_NUM]={0}, pre[MAX_VERTEX_NUM]={0};
	int weight[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int i, j, k, min;
	const int INF = 65535;
	for(i = 0; i <= graph.vexnum; i++)
		for(j = 0; j <= graph.vexnum; j++)
		{
			weight[i][j] = graph.arcs[i][j].adj;
			if(weight[i][j] == 0)
				weight[i][j] = INF;
		}
	visited[0] = true;
	for(i = 1; i < graph.vexnum; i++)
	{
		dist[i] = INF;
		pre[i] = 0;
	}
	for(i = 1; i < graph.vexnum; i++)
	{
		min = INF;
		k = 0;
		for(j = 1; j < graph.vexnum; j++)
			if(!visited[j] && min > dist[j])
			{
				min = dist[j];
				k = j;
			}
		visited[k] = true;
		for(j = 0; j < graph.vexnum; j++)
			if(!visited[j] && (dist[j] > dist[k]+weight[k][j]))
			{
				dist[j] = dist[k]+weight[k][j];
				pre[j] = k;
			}
	}
	cout << "Vex\tDist\tPre\t" << endl;
	for(i = 0; i < graph.vexnum; i++)
	{
		cout << graph.vexs[i] << "\t" << dist[i] << "\t" << graph.vexs[pre[i]] << endl;
	}
	return OK;
}